package al160getIntersectionNode;

import java.util.HashSet;
import java.util.List;

public class GetIntersectionNode {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        /*HashSet<ListNode> hashSet = new HashSet<>();

        ListNode p = headA;
        while (p!=null){
            hashSet.add(p);
            p=p.next;
        }
        p = headB;
        while (p!=null){
            if(hashSet.contains(p))
                return p;
            p= p.next;
        }

        return null;*/

        ListNode pa = headA;
        ListNode pb = headB;

        while (pa!=pb){
            pa = (pa==null)? headB:pa.next;
            pb = (pb==null)? headA:pb.next;
        }
        if (pa!=null)
            return pa;
        return null;
    }




    public static void main(String[] args) {
        // 创建链表A
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        ListNode intersect = new ListNode(8);  // 交点
        headA.next.next = intersect;
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);

        // 创建链表B
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next.next = intersect;  // 指向相同的交点

        ListNode intersection = getIntersectionNode(headA, headB);

        // 打印交点的值
        if (intersection != null) {
            System.out.println("The intersection node value is: " + intersection.val);
        } else {
            System.out.println("There is no intersection.");
        }
    }
}
